热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

C++|栈的应用(逆波兰算法)|计算器

后缀式的特点可用于计算表达式的值,我们通过中缀转后缀的方式可以将原表达式重新排列组合成为计算机易于理解的计算方式。详情请参考:逆波兰算法(

后缀式的特点可用于计算表达式的值,我们通过中缀转后缀的方式可以将原表达式重新排列组合成为计算机易于理解的计算方式。
详情请参考:逆波兰算法(后缀表达式)

关于中缀转后缀

中缀式转后缀式 如:
1+2就是一个中缀式,转换成后缀式为1 2 +
1+2*3…… ……1 2 3 * +
1+(2+5)…… ……1 2 5 + +

在计算时,从最左侧开始先选定一个符号该符号左边的两个数结合运算。以下(黄色高亮部分)计算过程如下

  • 1+2…… ……1 2 +

1与2进行+运算

  • 1+2*3…… ……1 2 3 * +

1. 最左边的符号 * ,左侧的两个数 2 3计算:2*3 = 6表达式:1 6 +
2. 最左边的符号 + ,左侧的两个数 1 6计算:1+6 = 7

  • 1+(2+5)…… ……1 2 5 + +

3. ...计算:2+5=7表达式:1 7 +
4. ...计算:1+7=8

如上所示,使用后缀式可以清晰的表示出表达式中的运算关系,所有运算符符号中,优先级最高的在最左边。

计算时从最左侧的符号先开始,且每个符号都与它左侧最近的两个数据结合

可以说,后缀式就是根据计算表达式中的优先级进行设计的。
比如,在计算表达式中 ’ ( ) ’ 的优先级最高,因此在转后缀式时遇到 ‘(’ 与 ‘)’ 之间的符号就认为是优先级最高的符号。

eg: a*(b+c)
a b c + *过程详解:
1、===a*(b+c)===↑
后缀: a ✔
符号:
2、===a*(b+c)===↑
后缀: a
符号: * ✔
3、===a*(b+c)===↑
后缀: a
符号: * ( ✔
4、===a*(b+c)===↑
后缀: a b ✔
符号: * (
5、===a*(b+c)===↑
后缀: a b
符号: * ( + ✔
6、===a*(b+c)===↑
后缀: a b c ✔
符号: * ( +
7、===a*(b+c)===↑
后缀: a b c
符号: * ( + ) ✔
注:遇到')',后面进来的符号都视为较低优先级符号,因此把' ( ) '内的符号全部转移到后缀式中
8、=============
后缀: a b c + ✔
符号: *
9、=============
后缀: a b c + * ✔
符号:

中缀转后缀技巧

中缀转后缀的核心就是,将优先级高的运算放在最前边计算,如 … (b+c)… 形式的表达式 ,要变成 … b c + … 。后缀式中优先级体现在符号自左向右的顺序,表达式的关系体现在每个符号与其左边最近的两个数字

而针对表达式 a+b-c ,因为 ‘+’ ‘-’ 优先级相同,而我们的计算顺序为同优先级自左向右,则我们认为左边的 ‘+’ 优先级更高。因此后缀式为 a b + c - ,其中 a b + 为(a+b) 就是原式中优先级高的部分。

而对于 a + b * c 的表达式,显然 b*c 的优先级最高,则后缀式为 a b c * + 。

在本例中,函数 void InfixToSuffix(); 进行中缀转后缀计算。

中缀转后缀计算机代码

#include using std::cin;
using std::cout;
using std::endl;template<typename T>
class Stack
{
public:Stack(int _m_size &#61; 20) :m_size(_m_size), mtop(0){data &#61; new T[m_size]();}~Stack(){delete[] data;}/* 判空 */bool empty(){return mtop &#61;&#61; 0;}void push(int val){if (Full()){throw std::exception("error: Stack is Full !");}data[mtop] &#61; val;mtop&#43;&#43;;}T top(){if (empty()){throw std::exception("error: The stack is empty !");}return data[mtop - 1];}void pop(){if (empty()){throw std::exception("error: Stack is Empty !");}mtop--;}void show(){if (empty()){cout << endl;}else{int i &#61; 0;while (i < mtop){cout << data[i] << " ";i&#43;&#43;;}cout << endl;}}
private:bool Full(){return mtop &#61;&#61; m_size;}T* data;int mtop;int m_size;
};/* 计算器类 */
class Calculator
{
public:// 这里m_size 默认给的是40&#xff0c;m_size限制表达式的长短Calculator(int _m_size &#61; 40) :m_size(_m_size), m_result(0){m_str &#61; new char[_m_size &#43; 1]();}~Calculator(){delete[] m_str;}/* 输入 */void setData(){cin.getline(m_str, m_size - 1); //最多输入m_size -1个&#xff0c;末尾加&#39;/0&#39;}/* 中缀转后缀 */void InfixToSuffix(); /* 把m_str输入的中缀式转换为后缀式 *//* 后缀计算 */void Compure();/* 计算结果 */double Getm_result(){return m_result;}
private:bool IsPop(char a, char b);char* m_str;double m_result;int m_size;};int main()
{while (1) {Calculator ca;ca.setData();ca.InfixToSuffix();ca.Compure();cout << ca.Getm_result() << endl;}return 0;
}// 比较符号优先级&#xff0c;是否出符号栈
// 栈顶元素b的优先级是否高于符号a&#xff0c; true/false 出栈b/入栈a
bool Calculator::IsPop(char a, char b) //a为待比较符号&#xff0c;b为符号栈栈顶元素
{if (b &#61;&#61; &#39;(&#39;) return false; //‘&#xff08;’优先级最低 if (a &#61;&#61; &#39;*&#39; || a &#61;&#61; &#39;/&#39;){if (b &#61;&#61; &#39;&#43;&#39; || b &#61;&#61; &#39;-&#39;){//可以入符号栈 // 栈外优先级高&#xff0c;可以继续入栈return false;}else{ return true;}}//if (a &#61;&#61; &#39;&#43;&#39; || a &#61;&#61; &#39;-&#39;)//{//a符号为最低优先级&#xff0c;符号栈出栈return true;//}
}/* 中缀转后缀 入栈 */
void Calculator::InfixToSuffix()
{// 转换为后缀式后&#xff0c;为了区分数字&#xff1a;如5、4……&#xff0c;在原来的数据增加了分隔符// dst 中存储输入的表达式的后缀式形式 size*2char* dst &#61; new char[m_size*2](); /* 符号栈 */Stack<char> symbol; // 在转后缀的过程中&#xff0c;&#xff08;通过符号优先级&#xff09;控制符号在后缀式中的位置int i &#61; 0;int k &#61; 0;while (m_str[i] !&#61; &#39;\0&#39;){/*----------- 特殊符号判断------------------------------*/if (m_str[i] &#61;&#61; &#39; &#39;) //如果当前字符是空格&#xff0c;则往后走一个{i&#43;&#43;;continue;}else if (m_str[i] &#61;&#61; &#39;(&#39;) //左括号直接入栈{symbol.push(m_str[i]);}else if (m_str[i] &#61;&#61; &#39;)&#39;) //遇到 &#xff09; &#xff0c;输出&#xff08; &#xff09;之间的所有符号{while (symbol.top() !&#61; &#39;(&#39;){dst[k&#43;&#43;] &#61; symbol.top();dst[k&#43;&#43;] &#61; &#39; &#39;;symbol.pop();}symbol.pop();}/*----------------- 数字 -------------------------------*/else if (isdigit(m_str[i])){dst[k&#43;&#43;] &#61; m_str[i];if (!isdigit(m_str[i &#43; 1])) //数字后加空格{dst[k&#43;&#43;] &#61; &#39; &#39;;}}/*----------------- 运算符 -------------------------------*/else{switch (m_str[i]){case &#39;&#43;&#39;:case &#39;-&#39;:case &#39;*&#39;:case &#39;/&#39;:if (symbol.empty()) //如果符号栈为空&#xff0c;直接入符号{symbol.push(m_str[i]);}else //否则&#xff0c;判断是否选择入符号栈还是出栈顶元素{// 栈内符号优先级高于栈外&#xff0c;出栈。 IsPop &#61;&#61; true;if (IsPop(m_str[i], symbol.top())) //出符号栈{dst[k&#43;&#43;] &#61; symbol.top();symbol.pop();continue;}else //当前符号优先级高&#xff0c;入符号栈{symbol.push(m_str[i]);}}break;default:break;}}i&#43;&#43;; /* 遍历下一字符 */}/*字符串已遍历完&#xff0c;把符号栈中剩余的符号入栈到数字栈中 */while (!symbol.empty()){dst[k&#43;&#43;] &#61; symbol.top();symbol.pop();}dst[k] &#61; &#39;\0&#39;;// 输出后缀式//cout <// 后缀表达式 保存到 Calculator::m_str中// 交换dst 与 m_str 的堆区空间char* tmp &#61; dst;dst &#61; m_str;m_str &#61; tmp; delete[]dst;
}void Calculator::Compure()
{/* 辅助栈 */Stack<double> st;int i &#61; 0;while (m_str[i] !&#61; &#39;\0&#39;){/*----------- 特殊符号判断------------------------------*/if (m_str[i] &#61;&#61; &#39; &#39;) //如果当前字符是空格&#xff0c;则往后走一个{i&#43;&#43;;continue;}/*----------------- 数字 -------------------------------*/else if (isdigit(m_str[i])){double tmp &#61; 0;while (m_str[i] !&#61; &#39; &#39;){tmp &#61; tmp * 10 &#43; m_str[i] - &#39;0&#39;;i&#43;&#43;;}st.push(tmp);}/*----------------- 运算符 -------------------------------*/else if (!st.empty()) //非空{double tmp &#61; 0;switch (m_str[i]){case &#39;&#43;&#39;:tmp &#43;&#61; st.top();st.pop();tmp &#43;&#61; st.top();st.pop();st.push(tmp);break;case &#39;-&#39;:tmp -&#61; st.top();st.pop();tmp &#43;&#61; st.top();st.pop();st.push(tmp);break;case &#39;*&#39;:tmp &#61; st.top();st.pop();tmp *&#61; st.top();st.pop();st.push(tmp);break;case &#39;/&#39;:{tmp &#61; st.top();st.pop();if (tmp !&#61; 0){tmp &#61; st.top() / tmp;st.pop();st.push(tmp);}else{throw std::exception("error: Divisor of 0 &#xff01;");}}break;default:break;}}i&#43;&#43;; /* 遍历下一字符 */}this->m_result &#61; st.top();st.top();
}

运行截图&#xff1a;
在这里插入图片描述

注&#xff1a;在计算器类中

Calculator(int _m_size &#61; 40) :m_size(_m_size), m_result(0)
{}

构造函数 _m_size 默认设置的为40&#xff0c;这将影响到我们输入的计算表达式的长度&#xff0c;我们在编译时可以根据需求自行更改代码。


推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • CentOS7源码编译安装MySQL5.6
    2019独角兽企业重金招聘Python工程师标准一、先在cmake官网下个最新的cmake源码包cmake官网:https:www.cmake.org如此时最新 ... [详细]
  • 深入理解 SQL 视图、存储过程与事务
    本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式,存储过程则封装了复杂的SQL逻辑,而事务确保了数据库操作的完整性和一致性。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 并发编程:深入理解设计原理与优化
    本文探讨了并发编程中的关键设计原则,特别是Java内存模型(JMM)的happens-before规则及其对多线程编程的影响。文章详细介绍了DCL双重检查锁定模式的问题及解决方案,并总结了不同处理器和内存模型之间的关系,旨在为程序员提供更深入的理解和最佳实践。 ... [详细]
author-avatar
cindy蔡79
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有